/*
题目: 滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

https://leetcode.cn/problems/sliding-puzzle/
 */
public class SlidingPuzzle {
    char[] cs = new char[6];
    int[] dir = new int[] {-3, 3, -1, 1};
    String tar = "123450";

    private static class Pair {
        String str ;
        int index ;
        public Pair(String str, int index) {
            this.str = str;
            this.index = index;
        }
    }

    public int slidingPuzzle(int[][] board) {
        int z = 0;  // 记录 0 的位置
        // 初识情况
        for (int i = 0, k = 0; i < 2; i ++) {
            for (int j = 0; j < 3; j ++) {
                cs[k ++] = (char) (board[i][j] + '0');
                if (board[i][j] == 0) z = i * 3 + j;
            }
        }

        // 单向广搜
        Set<String> set = new HashSet<> ();
        Queue<Pair> queue = new LinkedList<> ();

        String start = new String(cs);
        if (start.equals(tar))  return 0;
        queue.offer(new Pair(start, z));
        set.add(start);

        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                Pair cur = queue.poll();
                String curStr = cur.str;
                char[] curCs = curStr.toCharArray();
                z = cur.index;

                for (int i = 0; i < 4; i ++) {
                    int nextIndex = z + dir[i];
                    // 超界, 或者 不合法 移动
                    if (nextIndex < 0 || nextIndex > 5 || (z == 2 && nextIndex == 3) || (z == 3 && nextIndex == 2))   continue ;
                    swap(curCs, z, nextIndex);
                    String nextStr = new String(curCs);
                    if (nextStr.equals(tar))    return steps;

                    if (!set.contains(nextStr)) {
                        queue.offer(new Pair(nextStr, nextIndex));
                        set.add(nextStr);
                    }
                    swap(curCs, z, nextIndex);
                }
            }

            steps ++;
        }
        return -1;
    }

    private void swap(char[] c, int a, int b) {
        char t = c[a];
        c[a] = c[b];
        c[b] = t;
    }
}
